package findKthPositive;

public class Solution {
    public int findKthPositive(int[] arr, int k) {
//        int index = 0; // 表示第k个缺失的数字
//        int i = 1; // 表示从1-n的正整数
//        int lost = 0; // 表示缺失的数字
//        int j = 0;
//        while (index<k){
//            if(j<arr.length&&arr[j] == i){
//                j++;
//            }else {
//                lost = i;
//                index++;
//            }
//            i++;
//        }
//        return lost;

        // 二分查找
        if (arr[0] > k) {
            return k;
        }
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            int x = mid < arr.length ? arr[mid] : Integer.MAX_VALUE;
            if (x - mid - 1 >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1];
    }
}
